package Algorithm.dijkstra;

import java.util.Arrays;

//迪杰斯特拉算法，用于解决最短路径问题，计算一个节点到其他节点路径和最短问题
public class DijkstraAlgorithm {
	public static void main(String[] args) {
		char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
		//设置邻接矩阵,用 N 表示两点距离很大，不连通
		final int N = 65535;
		int[][] matrix = {{N, 5, 7, N, N, N, 2},
				{5, N, N, 9, N, N, 3},
				{7, N, N, N, 8, N, N},
				{N, 9, N, N, N, 4, N},
				{N, N, 8, N, N, 5, 4},
				{N, N, N, 4, 5, N, 6},
				{2, 3, N, N, 4, 6, N}};

		Graph graph = new Graph(vertexs, matrix);
		graph.showMatrix();

		graph.Dijkstra(0);
		graph.showResult();
	}

}

class Graph {
	//顶点数组
	private char[] vertex;
	//邻接矩阵
	private int[][] matrix;

	private VisitedVertex visitedVertex;

	//构造器
	public Graph(char[] vertex, int[][] matrix) {
		//初始化顶点
		this.vertex = new char[vertex.length];
		for (int i = 0; i < vertex.length; i++) {
			this.vertex[i] = vertex[i];
		}

		//初始化边
		this.matrix = new int[vertex.length][vertex.length];
		for (int i = 0; i < vertex.length; i++) {
			for (int j = 0; j < vertex.length; j++) {
				this.matrix[i][j] = matrix[i][j];
			}
		}
	}

	public void showMatrix() {
		for (int i = 0; i < vertex.length; i++) {
			for (int j = 0; j < vertex.length; j++) {
				System.out.printf("%6d", matrix[i][j]);
			}
			System.out.println();
		}
	}

	//显示结果
	public void showResult() {
		visitedVertex.showResult();
	}

	//迪杰斯特拉算法 =======================================
	//更新 index顶点 到周围顶点的距离和 周围顶点的前驱
	public void updateVertx(int index) {
		int length = 0;
		//遍历 邻接矩阵 中 index顶点 对应的行，得到到相邻的顶点的距离
		for (int j = 0; j < matrix[index].length; j++) {
			// 目标顶点 到 index顶点 的距离 + 从 index顶点 到 j顶点的距离 的和
			length = visitedVertex.getDis(index) + matrix[index][j];
			//如果 j顶点 未访问过 且 length < 目标顶点到 j顶点 的距离，则更新距离
			if (!visitedVertex.isVisited(j) && length < visitedVertex.getDis(j)) {
				//更新 j顶点 的前驱为 index顶点
				visitedVertex.updatePre(j, index);
				//更新 目标顶点 到 j顶点 的距离
				visitedVertex.updateDis(j, length);
			}
		}
	}

	public void Dijkstra(int index) {
		visitedVertex = new VisitedVertex(vertex.length, index);
		//更新 index顶点 到周围顶点的距离 和 前驱
		updateVertx(index);

		for (int i = 1; i < vertex.length; i++) {
			//选择并返回 下一个顶点
			index = visitedVertex.updateArray();
			//更新 index顶点 到周围顶点的距离 和 前驱
			updateVertx(index);
		}
	}

	//====================================================
}

//已经访问顶点的集合
class VisitedVertex {
	//记录各个顶点是否访问过，1 ：已访问；0 ：未访问
	public int[] alreadyArr;
	//记录每个顶点的前驱
	public int[] preVisited;
	//记录目标顶点，到所有顶点的距离，会动态更新为最短距离
	public int[] distance;

// ==============核+心=====================================

	/**
	 * @param lenght 顶点的个数
	 * @param index  目标顶点的下标
	 */
	public VisitedVertex(int lenght, int index) {
		this.alreadyArr = new int[lenght];
		this.preVisited = new int[lenght];
		this.distance = new int[lenght];
		//初始化 distance 把所有距离设为最大值
		Arrays.fill(distance, 65535);
		//把到自己的距离设为 0
		this.distance[index] = 0;
		//设置目标顶点被访问
		this.alreadyArr[index] = 1;
	}

	//继续选择 并 返回新的访问顶点
	public int updateArray() {
		int min = 65535;
		int index = 0;
		for (int i = 0; i < alreadyArr.length; i++) {
			if (!isVisited(i) && distance[i] < min) {
				min = distance[i];
				index = i;
			}
		}
		//更新 index顶点 已被访问
		alreadyArr[index] = 1;

		return index;
	}

// =======================================================


	//显示最后结果,即三个数组的情况
	public void showResult() {
		System.out.println("====顶点被访问情况=====");
		for (int i : alreadyArr) {
			System.out.print(i + " ");
		}
		System.out.println();

		System.out.println("====个顶点前驱=====");
		for (int i : preVisited) {
			System.out.print(i + " ");
		}
		System.out.println();

		System.out.println("====各个顶点到目标顶点距离=====");
		for (int i : distance) {
			System.out.print(i + " ");
		}
		System.out.println();
	}


	/**
	 * 判断 index 顶点是否被访问过
	 *
	 * @param index
	 * @return 若访问过 返回 true 否则返回 false
	 */
	public boolean isVisited(int index) {
		return alreadyArr[index] == 1;
	}

	/**
	 * 更新（目标顶点）到（下标为index的顶点）的距离
	 *
	 * @param index
	 * @param length
	 */
	public void updateDis(int index, int length) {
		distance[index] = length;
	}

	/**
	 * 更新 preIndex顶点 的前驱为 index顶点
	 *
	 * @param preIndex
	 * @param index
	 */
	public void updatePre(int preIndex, int index) {
		preVisited[preIndex] = index;
	}

	/**
	 * 返回出发顶点到 index顶点 距离
	 *
	 * @param index
	 */
	public int getDis(int index) {
		return distance[index];
	}
}
